class Solution {
public:
    int rob1(vector<int>& nums)
    {
        if (nums.size() == 1)return nums[0];
        vector<int>dp(nums.size());
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for (int i = 2; i < nums.size(); i++)
        {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        int maxp = 0;
        for (int i = 0; i < nums.size(); i++)
        {

            if (dp[i] > maxp)
                maxp = dp[i];
        }
        return maxp;
    }








    int rob(vector<int>& nums) {
        if (nums.size() == 1)
            return nums[0];
        if (nums.size() == 2)
            return  max(nums[0], nums[1]);
        vector<int>nums1(nums.begin(), nums.end() - 1);
        vector<int>nums2(nums.begin() + 1, nums.end());
        vector<int>nums3(nums.begin() + 1, nums.end() - 1);
        int a = rob1(nums1);
        int b = rob1(nums2);
        int c = rob1(nums3);
        return max(max(a, b), c);







    }
};/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rob1(TreeNode* root) {
        if (root == nullptr)
            return vector<int>{0, 0};

        vector<int>leftdp = rob1(root->left);
        vector<int>rightdp = rob1(root->right);
        int val1 = root->val + leftdp[0] + rightdp[0];
        int val2 = max(leftdp[0], leftdp[1]) + max(rightdp[0], rightdp[1]);
        return { val2,val1 };

    }


    int rob(TreeNode* root) {
        vector<int>result = rob1(root);
        return max(result[0], result[1]);














    }
}; class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>>dp(s.size(), vector<bool>(s.size(), false));
        int result = 0;
        for (int i = s.size() - 1; i >= 0; i--)
        {
            for (int j = i; j < s.size(); j++)
            {
                if (s[i] == s[j])
                {
                    if (j - i <= 1)
                    {
                        dp[i][j] = true;
                        result++;




                    }
                    else
                    {
                        if (dp[i + 1][j - 1] == true)
                        {
                            dp[i][j] = true;
                            result++;
                        }





                    }










                }
                else
                {




                }












            }








        }
        return result;











    }
}; class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>>dp(s.size(), vector<bool>(s.size(), false));
        int result = 0;
        for (int i = s.size() - 1; i >= 0; i--)
        {
            for (int j = i; j < s.size(); j++)
            {
                if (s[i] == s[j])
                {
                    if (j - i <= 1)
                    {
                        dp[i][j] = true;
                        result++;




                    }
                    else
                    {
                        if (dp[i + 1][j - 1] == true)
                        {
                            dp[i][j] = true;
                            result++;
                        }





                    }










                }
                else
                {




                }












            }








        }
        return result;











    }
}; class Solution {
public:
    string longestPalindrome(string s) {
        vector<vector<bool>>dp(s.size(), vector<bool>(s.size(), false));
        int result = 0;
        int remi = 0;
        int remj = 0;
        int lenth = 1;
        for (int i = s.size() - 1; i >= 0; i--)
        {
            for (int j = i; j < s.size(); j++)
            {
                if (s[i] == s[j])
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                if (dp[i][j] && j - i + 1 > lenth)
                {
                    lenth = j - i + 1;
                    remi = i;
                }
            }



        }












        return s.substr(remi, lenth);







    }

}; class Solution {
public:
    bool checkPartitioning(string s) {

        vector<vector<bool>>dp(s.size(), vector<bool>(s.size(), false));

        for (int i = s.size() - 1; i >= 0; i--)
        {
            for (int j = i; j < s.size(); j++)
            {
                if (s[i] == s[j])
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;

            }
        }


        for (int i = 1; i < s.size() - 1; i++)
        {
            for (int j = i; j < s.size() - 1; j++)
            {
                if (dp[0][i - 1] && dp[i][j] && dp[j + 1][s.size() - 1])
                    return true;

            }
        }
        return false;
    }
}; class Solution {
public:
    string longestPalindrome(string s) {
        vector<vector<bool>>dp(s.size(), vector<bool>(s.size(), false));
        int result = 0;
        int remi = 0;
        int remj = 0;
        int lenth = 1;
        for (int i = s.size() - 1; i >= 0; i--)
        {
            for (int j = i; j < s.size(); j++)
            {
                if (s[i] == s[j])
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                if (dp[i][j] && j - i + 1 > lenth)
                {
                    lenth = j - i + 1;
                    remi = i;
                }
            }



        }












        return s.substr(remi, lenth);







    }

}; class Solution {
public:
    int minCut(string s) {
        vector<vector<bool>>res(s.size(), vector<bool>(s.size(), false));
        for (int i = s.size() - 1; i >= 0; i--)
        {
            for (int j = i; j < s.size(); j++)
            {
                if (s[i] == s[j])
                {
                    res[i][j] = i + 1 < j ? res[i + 1][j - 1] : true;

                }





            }

        }

        vector<int>dp(s.size(), INT_MAX);
        for (int i = 0; i < s.size(); i++)
        {
            if (res[0][i]) dp[i] = 0;
            else
            {
                for (int j = 1; j <= i; j++)
                {
                    if (res[j][i])
                        dp[i] = min(dp[i], dp[j - 1] + 1);
                }







            }







        }






        return dp[s.size() - 1];





    }
}; class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>>dp(s.size(), vector<int>(s.size(), 0));
        for (int i = 0; i < s.size(); i++)
        {
            dp[i][i] = 1;
        }
        for (int i = s.size() - 1; i >= 0; i--)
        {
            for (int j = i + 1; j < s.size(); j++)
            {
                if (s[i] == s[j])
                {
                    dp[i][j] = dp[i + 1][j - 1] + 2;




                }
                else
                {

                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

                }




            }




        }







        return dp[0][s.size() - 1];




    }
}; class MinStack {
public:
    MinStack() {

    }

    void push(int val) {
        st.push(val);
        if (min.empty() || val <= min.top())
        {
            min.push(val);
        }

    }

    void pop() {

        if (st.top() == min.top())
        {
            min.pop();

        }
        st.pop();




    }

    int top() {
        return st.top();

    }

    int getMin() {
        return min.top();

    }
    stack<int> st;
    stack<int> min;

};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */class Solution {
 public:
     bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
         stack<int>pushst;

         int pushi = 0;

         int popi = 0;



         while (pushi < pushed.size())

         {

             pushst.push(pushed[pushi++]);

             while (!pushst.empty() && pushst.top() == popped[popi])

             {

                 pushst.pop();

                 popi++;



             }



         }

         return pushst.empty();


     }
 }; class Solution {
 public:
     int evalRPN(vector<string>& tokens) {
         stack<int>st;
         for (auto& e : tokens)
         {

             if (e == "+" || e == "-" || e == "*" || e == "/")
             {
                 int right = st.top();
                 st.pop();
                 int left = st.top();
                 st.pop();

                 switch (e[0])
                 {
                 case '+':
                     st.push(left + right);
                     break;
                 case '-':
                     st.push(left - right);
                     break;
                 case '*':
                     st.push(left * right);
                     break;
                 case '/':
                     st.push(left / right);
                     break;
                 }

             }
             else
             {
                 st.push(stoi(e));
             }















         }
         return st.top();










     }
 }; class Solution {
 public:
     int massage(vector<int>& nums) {
         if (nums.size() == 0)
             return 0;
         if (nums.size() == 1)
             return nums[0];
         if (nums.size() == 2)
             return max(nums[0], nums[1]);
         vector<int>dp(nums.size());
         dp[0] = nums[0];
         dp[1] = max(nums[0], nums[1]);
         for (int i = 2; i < nums.size(); i++)
         {

             dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);




         }
         return dp[nums.size() - 1];









     }
 }; class Solution {
 public:
     int count = 1e4 + 1;
     int deleteAndEarn(vector<int>& nums) {
         int arr[count];
         for (int i = 0; i < count; i++)
             arr[i] = 0;


         for (auto e : nums)
         {
             arr[e] += e;
         }
         vector<int>dp(count, 0);

         dp[0] = arr[0];
         dp[1] = max(arr[0], arr[1]);


         for (int i = 2; i < count; i++)
         {
             dp[i] = max(dp[i - 2] + arr[i], dp[i - 1]);
         }
         return dp[count - 1];












     }
 }; class Solution {
 public:
     int minCost(vector<vector<int>>& costs) {
         vector<vector<int>>dp(costs.size() + 1, vector<int>(3));
         for (int i = 1; i <= costs.size(); i++)
         {
             dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
             dp[i][1] = min(dp[i - 1][2], dp[i - 1][0]) + costs[i - 1][1];
             dp[i][2] = min(dp[i - 1][1], dp[i - 1][0]) + costs[i - 1][2];
         }

         return min(min(dp[costs.size()][0], dp[costs.size()][1]), dp[costs.size()][2]);

     }
 };